package sort.quiksort;

import sort.mergesort.MergeSort;
import sort.util.RamdomUtil;
import sort.util.StopWatch;

/**
 * Created by asus on 2017/9/30.
 */
public class QuikSort {

    public static boolean less(int a, int b) {
        if (a < b) {
            return true;
        }
        return false;
    }

    public static void exchange(int[] a, int i, int j) {
        if (i != j) {
            int temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
    }


    public static int partition(int[] a, int lo, int hi) {
        int compare = a[lo], temp;
        int i = lo, j = hi + 1;
        while (true) {
            while (a[++i] < compare) {//找到 >= compare的数
                if (i == hi) break;
            }
            while (compare < a[--j]) {//找到 <= compare的数
                if (j == lo) break;
            }
            if (i >= j) break;
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
        temp = a[j];
        a[j] = a[lo];
        a[lo] = temp;
        return j;
    }

    public static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void main(String[] args) {
        StopWatch first = null;
        int[] mergedata = null;
        int[] quikdata = null;
        for (int inc = 1000000; inc <= 100000000; inc += 1000000) {
            mergedata = RamdomUtil.generateRandomArray(inc);
            quikdata = RamdomUtil.generateRandomArray(inc);
            first = new StopWatch(Integer.toString(inc / 10000));
            first.start("QuikSort");
            QuikSort.sort(quikdata);
            first.stop();
            first.start("MergeSort");
            MergeSort.sort(mergedata);
            first.stop();
            System.out.println(first.prettyPrint());
        }
    }
}
